#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
#include "LinkedListBinaryTree.h"
#include "../stack/Stack.h"

#define MAXSIZE 20

BinaryTree *initBinaryTree(ElemType data) {
    BinaryTree *node = malloc(sizeof *node);
    node->data = data;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

// 顺序存储初始化二叉树
BinaryTree *createBinaryTreeByArray(ElemType arrayData[], int size) {
    if (arrayData == NULL || size == 0) {
        return NULL;
    }
    BinaryTree *root = initBinaryTree(arrayData[0]);
    LinkedListBinaryTree *list = initLinkedListBinaryTree();
    BinaryTree *node = root;
    for (int i = 0; i <= size; i++) {
        // 没有孩子节点
        if (arrayData[i] == ' ' || i * 2 + 1 > size) {
            break;
        }
        // 左孩子
        if (arrayData[i * 2 + 1] != ' ') {
            node->lchild = initBinaryTree(arrayData[i * 2 + 1]);
            enBinaryTreeQueue(list, node->lchild);
        }
        // 右孩子

        if (i * 2 + 2 < size && arrayData[i * 2 + 2] != ' ') {
            node->rchild = initBinaryTree(arrayData[i * 2 + 2]);
            enBinaryTreeQueue(list, node->rchild);
        }
        node = deBinaryTreeQueue(list);
    }
    deleteLinkedListBinaryTree(list);
    return root;
}

// 括号表示法初始化二叉树-- A(B(D(,G)),C(E,F))
BinaryTree *createBinaryTreeByString(ElemType *str) {
    // 初始化堆
    int size = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(' || str[i] == ')' || str[i] == ',') {
            continue;
        }
        size++;
    }
    BinaryTree **binaryTree = malloc(size * sizeof(BinaryTree *));
    int n = 0;

    BinaryTree *root = NULL;
    BinaryTree *p = NULL;
    int k = 1;

    for (int j = 0; j < str[j] != '\0'; ++j) {
        switch (str[j]) {
            case '(':
                // 遇到'(' 入栈，并设置k=1
                binaryTree[n++] = p;
                k = 1;
                break;
            case ')':
                // 遇到')' 出栈，并设置k=1
                p = binaryTree[--n];
                k = 1;
                break;
            case ',':
                // 遇到‘，’，设置k=2
                k = 2;
                break;
            default:{
                BinaryTree *temp = initBinaryTree(str[j]);
                if (root != NULL) {
                    if (k == 1) {
                        binaryTree[n - 1]->lchild = temp;
                    } else {
                        binaryTree[n - 1]->rchild = temp;
                    }
                } else {
                    root = temp;
                }
                p = temp;
            }
        }
    }
    free(binaryTree);
    return root;
}

// 先序遍历
void preOrder(BinaryTree *root) {
    BinaryTree *binaryTree[MAXSIZE];
    int n = 0;
    // 根节点压栈
    binaryTree[n++] = root;
    printf("先序遍历：");
    while (n > 0) {
        // 弹栈
        BinaryTree *p = binaryTree[--n];
        printf("%c", p->data);
        // 右节点压栈
        if (p->rchild != NULL) {
            binaryTree[n++] = p->rchild;
        }
        // 左节点压栈
        if (p->lchild != NULL) {
            binaryTree[n++] = p->lchild;
        }
    }
    printf("\n");
}

// 中序遍历
void inOrder(BinaryTree *root) {
    BinaryTree *binaryTree[MAXSIZE];
    int n = 0;

    printf("中序遍历：");
    BinaryTree *p = root;
    while (p != NULL || n > 0) {
        // 遍历到无左节点
        while (p != NULL) {
            binaryTree[n++] = p;
            p = p->lchild;
        }

        // 回溯,并取右节点
        if (n > 0) {
            p = binaryTree[--n];
            printf("%c", p->data);
            p = p->rchild;
        }
    }
    printf("\n");
}

// 后序遍历
void postOrder(BinaryTree *root) {
    BinaryTree *binaryTree[MAXSIZE];
    int n = 0;

    BinaryTree *bt = root;
    BinaryTree *p;
    int flag;
    printf("后序遍历：");
    do {
        while (bt != NULL) {
            binaryTree[n++] = bt;
            bt = bt->lchild;
        }

        // 表示bt的左节点已经访问过或为空
        flag = 1;
        // 指向栈顶节点的前一个已访问的节点
        p = NULL;
        while (flag && n > 0) {
            if (binaryTree[n - 1]->rchild == p) {
                // 若 p = NULL ,表示右孩子不存在, 而左孩子不存在或者已访问，所以可以访问该节点
                // 若 p != NULL ,表示右孩子已访问过
                p = binaryTree[--n];
                printf("%c", p->data);
            } else {
                bt = binaryTree[n - 1]->rchild;
                flag = 0;
            }
        }
    } while (n > 0);
    printf("\n");
}


// 层次遍历
void levelOrder(BinaryTree *root) {
    // 采用环形队列
    BinaryTree *binaryTree[MAXSIZE];
    int font = 0;
    int rear = 0;
    BinaryTree *p = NULL;

    printf("层次遍历：");
    binaryTree[rear++] = root;
    while (rear % MAXSIZE != font) {
        p = binaryTree[font++ % MAXSIZE];
        printf("%c", p->data);
        if (p->lchild != NULL) {
            binaryTree[rear++ % MAXSIZE] = p->lchild;
        }
        if (p->rchild != NULL) {
            binaryTree[rear++ % MAXSIZE] = p->rchild;
        }
    }
    printf("\n");
}

// 释放内存 利用后序遍历
void deleteBinaryTree(BinaryTree *root) {
    BinaryTree *binaryTree[MAXSIZE];
    int n = 0;

    BinaryTree *bt = root;
    BinaryTree *p;
    do {
        while (bt != NULL) {
            binaryTree[n++] = bt;
            bt = bt->lchild;
        }

        int flag = 1;
        p = NULL;
        while (flag && n > 0) {
            if (binaryTree[n - 1]->rchild == p) {
                free(binaryTree[--n]);
                bt = p = binaryTree[n];
            } else {
                flag = 0;
                bt = binaryTree[n - 1]->rchild;
            }
        }
    } while (n > 0);
}

void binaryTreeTest() {
    char arrayData[MAXSIZE] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
                               ' ', 'T'};
    BinaryTree *root = createBinaryTreeByArray(arrayData, MAXSIZE);
//    root = createBinaryTreeByString("A(B(D(H,G)),C(E,F))");

    preOrder(root);
    inOrder(root);
    postOrder(root);
    levelOrder(root);

    deleteBinaryTree(root);
}